package com.atguigui.leetcode1;

import java.util.ArrayList;
import java.util.List;

/**
 * 1073.负二进制数相加
 * Project: leetcode
 * Package: com.atguigui.leetcode1
 * Version: 1.0
 * <p>
 * Created by WJX on 2023/5/18 10:56
 */
public class P1073AddingTwoNegabinaryNumbers {

    public static void main(String[] args) {
        Solution solution = new P1073AddingTwoNegabinaryNumbers().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] addNegabinary(int[] arr1, int[] arr2) {
            int i = arr1.length - 1, j = arr2.length - 1;
            int carry = 0;
            List<Integer> ans = new ArrayList<Integer>();
            while (i >= 0 || j >= 0 || carry != 0) {
                var x = carry;

                //从高位开始往后算
                if (i >= 0) {
                    x += arr1[i];
                }
                if (j >= 0) {
                    x += arr2[j];
                }

                //逢2进-1 变成0
                if (x >= 2) {
                    ans.add(x - 2);
                    carry = -1;
                } else if (x >= 0) {
                    ans.add(x);
                    carry = 0;
                } else {
                    ans.add(1);
                    carry = 1;
                }

                --i;
                --j;
            }
            //删除最后一位是0的
            while (ans.size() > 1 && ans.get(ans.size() - 1) == 0) {
                ans.remove(ans.size() - 1);
            }

            int[] arr = new int[ans.size()];
            for (i = 0, j = ans.size() - 1; j >= 0; i++, j--) {
                arr[i] = ans.get(j);
            }


            return arr;
        }
    }
}
